package LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
    给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
*/

public class Code102_levelOrder {

    /**
     * 使用广度优先搜索（BFS）按层级顺序遍历二叉树
     * 此方法通过队列来实现层级遍历，将每一层的节点逐个出队，并将其子节点按顺序入队，以实现层级遍历
     *
     * @param root 二叉树的根节点，如果根节点为空，则直接返回空列表
     * @return 返回一个列表的列表，其中每个列表代表二叉树每一层的节点值
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        // 初始化结果列表，用于存储每一层的节点值
        List<List<Integer>> res = new ArrayList<>();
        // 如果根节点为空，则直接返回空的结果列表
        if (root == null) {
            return res;
        }
        // 初始化队列，用于存储当前层的节点
        Queue<TreeNode> queue = new LinkedList<>();
        // 将根节点添加到队列中，作为第一层的唯一节点
        queue.add(root);
        // 初始化当前层的计数器为0，表示从第一层开始遍历
        int currentLevel = 0;
        // 当队列不为空时，表示还有节点未遍历完
        while (!queue.isEmpty()) {
            // 获取当前层的节点数量
            int size = queue.size();
            // 在结果列表中添加一个新的列表，用于存储当前层的节点值
            res.add(new ArrayList<>());
            // 遍历当前层的所有节点
            while (--size >= 0) {
                // 从队列中取出一个节点
                TreeNode cur = queue.poll();
                // 将该节点的值添加到当前层的结果列表中
                res.get(currentLevel).add(cur.val);
                // 如果当前节点有左子节点，将左子节点添加到队列中
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                // 如果当前节点有右子节点，将右子节点添加到队列中
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            // 当前层遍历完毕，层数计数器增加
            currentLevel++;
        }
        // 返回结果列表，其中包含了每一层的节点值
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        List<List<Integer>> res = levelOrder(root);

    }
}
